import java.util.Arrays;
import java.util.Random;

public class Test {
    /**
     * 排序
     * @param args
     *      1.排序的概念及引用
     *      2.常见排序的实现
     */
    //测试排序时间复杂度
    //乱序
    public static void initArray(int[] array) {
        Random random = new Random();
        for(int i = 0;i < array.length;i++) {
            array[i] = random.nextInt(array.length);
        }
    }
    //有序
    public static void inorderArray(int[] array) {
        for(int i = 0;i < array.length;i++) {
            array[i] = i;
        }
    }
    //逆序
    public static void notInorderArray(int[] array) {
        for(int i = 0;i < array.length;i++) {
            array[i] = array.length - i;
        }
    }
    //测试直接插入
    public static void testInsertSort(int[] array) {
        int[] tmp = Arrays.copyOf(array,array.length);
        long startTime = System.currentTimeMillis();
        Sort.insertSort(tmp);
        long endTime = System.currentTimeMillis();
        System.out.println("直接插入排序:" + (endTime - startTime));
    }
    //测试希尔插入
    public static void testShellSort(int[] array) {
        int[] tmp = Arrays.copyOf(array,array.length);
        long startTime = System.currentTimeMillis();
        Sort.shellSort(tmp);
        long endTime = System.currentTimeMillis();
        System.out.println("希尔排序:" + (endTime - startTime));
    }
    //测试直接选择
    public static void testSelectSort(int[] array) {
        int[] tmp = Arrays.copyOf(array,array.length);
        long startTime = System.currentTimeMillis();
        Sort.selectSort(tmp);
        long endTime = System.currentTimeMillis();
        System.out.println("直接选择排序:" + (endTime - startTime));
    }
    public static void testHeapSort(int[] array) {
        int[] tmp = Arrays.copyOf(array,array.length);
        long startTime = System.currentTimeMillis();
        Sort.heapSort(tmp);
        long endTime = System.currentTimeMillis();
        System.out.println("堆排序:" + (endTime - startTime));
    }
    public static void testBubbleSort(int[] array) {
        int[] tmp = Arrays.copyOf(array,array.length);
        long startTime = System.currentTimeMillis();
        Sort.bubbleSort(tmp);
        long endTime = System.currentTimeMillis();
        System.out.println("冒泡排序:" + (endTime - startTime));
    }

    public static void main(String[] args) {
        int[] array = new int[10000];
        //顺序
//        inorderArray(array);
        //逆序
//        notInorderArray(array);
        //乱序
        initArray(array);
        testInsertSort(array);
        testShellSort(array);
        testSelectSort(array);
        testHeapSort(array);
        testBubbleSort(array);
    }
    public static void main2(String[] args) {
        int[] array1 = {5,7,10,3,2};
        //直接插入排序
        Sort.insertSort(array1);
        System.out.println(Arrays.toString(array1));
        //希尔排序
        int[] array2 = {9,1,2,5,7,4,8,6,3,5};
        Sort.shellSort(array2);
        System.out.println(Arrays.toString(array2));
        //直接选择排序
        int[] array3 = {5,7,10,3,2};
        Sort.selectSort2(array3);
        System.out.println(Arrays.toString(array3));
        Sort.selectSort(array3);
        System.out.println(Arrays.toString(array3));
        //堆排序
        int[] array4 = {5,7,10,3,2};
        Sort.heapSort(array4);
        System.out.println(Arrays.toString(array4));
        //冒泡排序
        int[] array5 = {5,7,10,3,2};
        Sort.bubbleSort(array5);
        System.out.println(Arrays.toString(array5));
    }
    public static void main1(String[] args) {
        /**
         * 排序的概念
         *      将一个集合以某个/某些关键字按照递增/递减进行排序
         *      稳定性:相对次序不变->稳定 相对次序改变->不稳定
         *          例如 3 5(a代表一个标记)  5(b) 排序后:结果1:3 5(a)  5(b)->稳定 结果2:3 5(b)  5(a)->不稳定
         *      内部排序:数据元素全部放在内存中的排序
         *      外部排序:数据元素太多,不能同时放在内存中,放在磁盘或其它地方,且排序过程中,不能两个地方相互移动
          */
        /**
         * 常见排序算法
         *      插入排序:直接插入 希尔排序
         *      选择排序:选择排序 堆排序
         *      交换排序:冒泡排序 快速排序
         *      归并排序:归并排序
         */
    }
}
